package com._23DesignPattern._algorithm._sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @Author: huangya
 * @Date: 2019/4/24
 * @Description:
 */
public class BinaryTree {
    static int SIZE = 20000;

    private static List<Integer> list = new ArrayList<>(SIZE);
    private static List<Integer> list2 = new ArrayList<>(SIZE);
    private static Integer[] integers = new Integer[SIZE];
    private static Integer[] integers2 = new Integer[SIZE];

    static {
        for(int i=0;i<SIZE;i++){
            list.add(i);
            list2.add(i);
        }
        Collections.shuffle(list);
        integers = list.toArray(integers);

        Collections.shuffle(list2);
        integers2 = list2.toArray(integers2);
    }

    public class Node {          //声明一个节点类
        private Comparable data;  //节点的数据类型为Comparable
        private Node left;   //保存左子树
        private Node right;  //保存右子树

        public Node(Comparable data) {   //构造函数
            this.data = data;
        }

        public void addNode(Node newNode) {
            //确定是放在左子树还是右子树
            if (newNode.data.compareTo(this.data) < 0) {  //新节点值小于当前节点
                if (this.left == null) {
                    this.left = newNode;  //左子树为空的话，新节点设为左子树
                } else {
                    this.left.addNode(newNode); //否则继续向下判断
                }
            } else {  //新节点的值大于或等于当前节点
                if (this.right == null) {
                    this.right = newNode;
                } else {
                    this.right.addNode(newNode);
                }
            }
        }

        public void printNode() {  //采用中序遍历
            if (this.left != null) {   //如果不为空先输出左子树
                this.left.printNode();
            }
            System.out.print(this.data + "\t");  //输出当前根节点
            if (this.right != null) {  //输出右子树
                this.right.printNode();
            }
        }
    }

    private Node root;    //表示根元素

    public void add(Comparable data) {    //向二叉树中插入元素
        Node newNode = new Node(data);
        if (root == null) {   //没有根节点
            root = newNode;
        } else {
            root.addNode(newNode); //判断放在左子树还是右子树
        }
    }

    public void print() {
        root.printNode();   //根据根节点输出
    }


    public static void main(String args[]) {
        long start = System.currentTimeMillis();
        BinaryTree bt = new BinaryTree();
        for(Integer item : integers){
            bt.add(item);
        }
        bt.print();
//        bt.add(4);
//        bt.add(3);
//        bt.add(5);
//        bt.add(1);
//        bt.add(2);
//        bt.add(8);
//        bt.add(7);
//        bt.add(8);
//        bt.add(1);
//        bt.print();
        System.out.println();
        long end = System.currentTimeMillis();
        System.out.println(end-start);


//        long start2 = System.currentTimeMillis();
//        for(int i=0;i<integers2.length;i++){
//            for(int j=0;j<integers2.length-i-1;j++){
//                if(integers2[j]>integers2[j+1]){
//                    int tmp = integers2[j+1];
//                    integers2[j+1] = integers2[j];
//                    integers2[j] = tmp;
//                }
//            }
//        }
//        for(Integer item : integers2){
//            System.out.print(item);
//        }
//        System.out.println();
//        long end2 = System.currentTimeMillis();
//        System.out.println(end2-start2);

    }


}
